0581. 最短无序连续子数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 一次扫描

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，你需要找出一个 连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

---

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

---

提示：

• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

2. 🎯 s.1 - 一次扫描

c

#include <limits.h>

int findUnsortedSubarray(int* nums, int numsSize) {
    int maxVal = INT_MIN, minVal = INT_MAX;
    int left = -1, right = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < maxVal) right = i;
        else maxVal = nums[i];
    }
    for (int i = numsSize - 1; i >= 0; i--) {
        if (nums[i] > minVal) left = i;
        else minVal = nums[i];
    }
    return right == -1 ? 0 : right - left + 1;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function (nums) {
  const n = nums.length
  let maxVal = -Infinity,
    minVal = Infinity
  let left = -1,
    right = -1
  for (let i = 0; i < n; i++) {
    if (nums[i] < maxVal) right = i
    else maxVal = nums[i]
  }
  for (let i = n - 1; i >= 0; i--) {
    if (nums[i] > minVal) left = i
    else minVal = nums[i]
  }
  return right === -1 ? 0 : right - left + 1
}

py

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        max_val, min_val = float('-inf'), float('inf')
        left = right = -1
        for i in range(n):
            if nums[i] < max_val:
                right = i
            else:
                max_val = nums[i]
        for i in range(n - 1, -1, -1):
            if nums[i] > min_val:
                left = i
            else:
                min_val = nums[i]
        return 0 if right == -1 else right - left + 1

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(1)$

算法思路：

• 从左向右遍历，维护左侧最大值，最后一个小于左侧最大值的位置即为右边界
• 从右向左遍历，维护右侧最小值，最后一个大于右侧最小值的位置即为左边界